package com.cuz.series.linklist;

/***
 * https://leetcode.cn/problems/partition-list-lcci/ 进阶版本
 */
public class 链表4单链表按某值划分为小于等于大于的部分 {
    public static void main(String[] args) {
        ListNode node = ListNode.of1( 5, 7, 11, 10,2, 3, 1);
        partition(node,5).print();
    }

    public static ListNode partition(ListNode node, int val) {
        if (node == null || node.next == null) {
            return node;
        }
        //小于部分的头
        ListNode lessHead = null;
        //小于部分的尾巴
        ListNode lessTail = null;
        //等于部分的头
        ListNode equalHead = null;
        //等于部分的尾巴
        ListNode equalTail = null;
        //大于部分的头
        ListNode betterHead = null;
        //大于部分的尾
        ListNode betterTail = null;
        while (node != null) {
            int v = node.val;
            if (v == val) {
                //等于头尾和当前节点连接起来，返回[新头，新尾]
                ListNode[] link = link(equalHead, equalTail, node);
                equalHead = link[0];
                equalTail = link[1];
                //断开node 和下一个节点的指针 并且让node走到下一个节点的位置
                node = unlinkAndNext(node);
                continue;
            }

            if (v < val) {
                //小于头 尾 和当前节点连接起来，返回[新头，新尾]
                ListNode[] link = link(lessHead, lessTail, node);
                lessHead = link[0];
                lessTail = link[1];
            } else {
                //大于头 尾 和当前节点连接起来，返回[新头，新尾]
                ListNode[] link = link(betterHead, betterTail, node);
                betterHead = link[0];
                betterTail = link[1];
            }

            //断开node 和下一个节点的指针 并且让node走到下一个节点的位置
            node = unlinkAndNext(node);
        }
        //连接小于尾 和等于头 返回新的头和尾巴
        ListNode[] cArray = connect(lessHead, lessTail, equalHead, equalTail);
        //连接大于的部分
        return connect(cArray[0], cArray[1], betterHead, betterTail)[0];
    }

    /***
     *断开连接并且向前移动
     */
    private static ListNode unlinkAndNext(ListNode node){
        ListNode temp = node.next;
        node.next=null;
        return temp;
    }

    /**
     * 连接返回新的头和尾巴
     * @param lessHead 小于头
     * @param lessTail 小于尾巴
     * @param betterHead 等于头
     * @param betterTail 等于尾巴
     */
    private static ListNode[] connect(ListNode lessHead, ListNode lessTail, ListNode betterHead, ListNode betterTail) {
        //没有小于部分 那么直接返回大于的头和尾巴
        if (lessHead == null) {
            return new ListNode[]{betterHead, betterTail};
        }
        //没有大于部分直接返回小于部分的头和尾巴
        if (betterHead == null) {
            return new ListNode[]{lessHead, lessTail};
        }

        // 小于和大于的部分都存在
        //连接小于尾和大于头
        lessTail.next=betterHead;
        //返回小于头 和 大于尾
        return new ListNode[]{lessHead, betterTail};
    }

    /***
     * 把当前节点插入到链表中
     * 返回新头尾
     * @param head 链表头
     * @param tail 链表尾
     * @param curNode
     * @return 新头尾
     */
    private static ListNode[] link(ListNode head, ListNode tail, ListNode curNode) {

        //之前链表没有初始化
        //比如当前式小于头 和尾 连接小于val的节点curNode，说明curNode是第一个出现的小于节点
        //那么curNode 作为头和尾
        if (head == null) {
            return new ListNode[]{curNode, curNode};
        }
        //连接 并返回
        tail.next = curNode;
        tail = tail.next;
        return new ListNode[]{head, tail};
    }

}
